The present invention is related to the field of finding, in response to a given search key such as an IP address, an entry in a stored table for determining further handling or forwarding of an item carrying that search key. In particular, the invention is concerned with compressing stored tables and optimizing the search for entries in the tables matching the given search key.
Longest matching prefix (LPM) searches are widely used, in particular for routing packets in the Internet according to assigned IP addresses. Many solutions have been suggested for comparing leading search key bits (prefixes) against stored prefixes, and finding the longest matching prefix with its associated output route information (or next hop pointer) in a stored data structure. In particular, search trees have found application for longest matching prefix searching.
A very straightforward LPM search scheme consists of using the search key as an index into a table that contains the search result for every possible value of the search key.
FIG. 1 illustrates an example of this method applied for an IP version 4 forwarding in which the search key consists of the 32-bit IP destination address. In this example the routing table contains the following prefixes:
The table contains 232 entries, one entry for each possible value of the 32-bit IP destination address. All valid entries (i.e., entries that will result in a valid search result A, B, C or D) are shown in FIG. 1. All other entries are regarded as invalid and result in an invalid search result. Entries can be identified as valid or invalid for example using a bit flag.
The main disadvantage of this LPM scheme is its inefficient usage of a large amount of storage. As FIG. 1 shows, the table contains 232 entries from which only a few are valid entries containing actual information related to the stored prefixes. A second disadvantage is that information related to a short prefix is stored in multiple table entries, which requires multiple memory accesses for insertion and removal of that prefix. This is the case with the fourth prefix (ABCDEh) that covers 212=4096 table entries (ABCDE000h to ABCDEFFFh) in FIG. 1.
These two disadvantages can be reduced by converting the single table that is indexed by the entire search key, into a treelike structure of multiple linked tables that are indexed by smaller parts of the search key. This approach has been described by Gupta et al. (xe2x80x9cRouting Lookups in Hardware at Memory Access Speeds.xe2x80x9d, Pankaj Gupta, Steven Lin, and Nick McKeown, IEEE Infocom April 1998, Vol 3, pp. 1240-1247, San Francisco) and Varghese et al. (xe2x80x9cFast address lookups using controlled prefix expansion.xe2x80x9d, V. Srinivasan and G. Varghese, ACM Trans. Comput. Syst. 17, 1, Feb. 1999, pp. 1-40).
FIG. 2 illustrates an example of applying such a concept on the data structure of FIG. 1. In FIG. 2 the search key is divided into three segments consisting of 16, 8 and 8 bits which are used to index the tables at the corresponding three levels as shown in FIG. 2. Each of these tables can contain valid and invalid entries, where a valid entry can contain a pointer to a table at the next level or a search result, and an invalid entry indicates an invalid search result.
The search operation starts with using the first segment as index into the table at level 1. If the indexed entry contains a pointer to a table at the next level, then this table will be indexed using the next segment. The search operation ends when an entry is indexed that contains a search result, which then will be the result of the search operation, or when an invalid entry is indexed in which case the result of the search operation will be an invalid result.
This is now illustrated for an IP destination address equal to xe2x80x9812345678hxe2x80x99. In FIG. 2 the first segment of this IP destination address equals xe2x80x981234hxe2x80x99 which is used as index into the table at level 1. This entry points to the lower table at level 2 in FIG. 2, which is indexed by the second segment of the IP destination address which equals xe2x80x9856hxe2x80x99. This entry points to the only table at level 3 in FIG. 2, which is then indexed using the third segment of the IP destination address which equals xe2x80x9878hxe2x80x99. This entry now provides the search result xe2x80x98Bxe2x80x99. The search results for the other prefixes are obtained in a similar way.
The data structure in FIG. 2 consists of 65536 table entries at level 1, 2*256=512 table entries at level 2, and 1*256 table entries at level 3, resulting in a total of 66304 table entries which is much less than the 232 table entries of the data structure of FIG. 1. Although the entries in both figures might not be the same (e.g., the entries in FIG. 2 need to able to store a pointer together with an indication whether a pointer or a search result is stored), the data structure of FIG. 2 has clearly much less storage requirements than the data structure of FIG. 1. Furthermore, information related to a short prefix is stored in fewer table entries resulting in fewer memory accesses for update operations. For example, now the fourth prefix (ABCDEh) covers only 17 table entries (ABCDh in the table at level 1 and E0h to EFh in the upper table at level 2) instead of 4096 entries in the data structure of FIG. 1.
The scheme shown in FIG. 2 can require more memory accesses for a single search operation than the scheme shown in FIG. 1. However, if all tables belonging to the same level are stored in a separate independently accessible memory bank, then pipelining can be applied to obtain the same number lookups per time unit as the scheme shown in FIG. 2.
The actual storage requirements of the data structure in FIG. 2 are dependent on the number and sizes of the segments in the IP destination address and the prefixes stored in the data structure. Both McKeown and Varghese describe schemes with a fixed number of fixed-size segments (as shown in FIG. 2) as well as schemes with a variable number of variable-size segments. In the latter type of schemes, segment size information is embedded within the table entries that contain pointers to the tables at the next level. In this way, search operations for different IP destination addresses that take different paths through the data structure can involve a different number of segments that have different sizes. Consequently, the sizes of the tables at the same level can be different.
The schemes with a variable number of variable-size segments, allow a better optimization of the storage requirements of the data structure. However, the update function is much more complex, especially the support of incremental updates, and takes much more time. If the tables at the various levels are stored in separate memory banks to allow pipelining as mentioned above, then the update operation for a scheme with a variable number of variable-size segments could involve data movement between different banks when the update operation would change the segment sizes along a certain path through the data structure. This results in less efficient use of memory bandwidth, which is a critical resource in many search engines today, and consequently in decreased update performance. Another way to optimize the storage requirements is described in U.S. Pat. No. 5,781,772 (Wilkinson et al.). This patent describes a mechanism called pointer compression, which is applied on a fixed-size set of pointers in a node. The mechanism involves that the xe2x80x98invalidxe2x80x99 pointers (NIL-pointers) are removed from the node and that the location of the valid pointers (non-NIL-pointers) can be determined using a bit mask that is added to each node and that indicates which pointers are existing in a node (i.e., non-NIL-pointers). The same mechanism could be applied to a table as shown in FIG. 2. A similar method is described in U.S. Pat. No. 5,813,001 (Bennett).
This type of compression will work well for tables with a small number of entries. Larger tables require larger bit masks which will result in larger storage requirements and slower processing time during the search operation. A second disadvantage is that the resulting tables can have any size, not necessarily a power-of-2. This will make buffer management more complex, since buffer sizes that are not a power-of-2 are more difficult to manage efficiently.
It is an object of the invention to devise a method (and a data structure) for finding, in response to a given search key, a matching entry in a stored data structure, which allows improved searching by compressing data tables in response to the distribution of the data actually stored, and which provides an optimized procedure for the search operation. It is a further object to find a search method which allows the use of variable-length index values for table accessing individually and optimally selected from given search key segments.
The invention for achieving these objects is defined in the claims. It provides, in particular, the use of selected or masked-out bits of a fixed-length search key segment to access optimally compressed tables of test values to be compared to a given search key segment. In a particular embodiment, the invention provides an efficient procedure for generating an optimum index mask for the selection of bits from a search key segment. In a further particular embodiment, an additional prefix mask is provided for selecting only those bits of test values which are actually necessary for comparison to a given search key segment.
The main advantages of the invention are shorter search times and savings in storage space. Furthermore, due to the use of fixed-length search key segments (despite a variable number of search key bits actually used), updating of the stored tables is simplified. The possible incremental updating results in lower storage requirements. Further, due to the use of power-of-two buffer sizes, buffer management is simplified, and memory is more efficiently used.
In the following, an embodiment of the invention will be described with reference to the accompanying drawings.